package com.example.Arithmetic.Arithmetic;

import java.util.ArrayList;
import java.util.List;

/**
 * 日期：2023/10/18
 * 时间：14:36
 * 描述：AVL树，平衡二叉树
 * 自平衡二叉树，左右高度相差不能超过1
 */
public class AVLTree {
    AVLNode root;

    static class AVLNode {
        int key;
        Object value;
        int height = 1;
        AVLNode left;
        AVLNode right;

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode() {
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 获取节点高度
     */
    private int getHeight(AVLNode avlNode) {
        return avlNode == null ? 0 : avlNode.height;
    }

    /**
     * @param node 更新树高度
     */
    private void updateHeight(AVLNode node) {
        node.height = Integer.max(getHeight(node.left), getHeight(node.right)) + 1;
    }

    /**
     * @param node
     * @return Height
     * 平衡因子(balance factor)
     * 平衡因子=左树高度-右树高度
     * bf=-1，0，1时为左右平衡
     * bf>1，bf<-1为不平衡
     * bf>1左边高，bf<-1右边高
     */
    private int bf(AVLNode node) {
        return getHeight(node.left) - getHeight(node.right);
    }

    /**
     * @param node
     * @return 右旋，LL
     * 左边高L，左边左孩子高L
     */
    private AVLNode rightRotate(AVLNode node) {
//        左节点
        AVLNode left = node.left;
//        左节点右孩子
        AVLNode right = left.right;
//        主节点左孩子变为左节点右孩子
        node.left = right;
//        换爹
        left.right = node;
//        调整根节点高度
        updateHeight(node);
//        调整后继根节点高度
        updateHeight(left);
        return left;
    }

    /**
     * @param node
     * @return 左旋，RR
     * 右边高R，右边左孩子高R
     */
    private AVLNode leftRotate(AVLNode node) {
//        右节点
        AVLNode right = node.right;
//        右节点左孩子
        AVLNode left = right.left;
//        主节点左孩子变为节点右孩子
        node.right = left;
//        换爹
        right.left = node;
        //        调整根节点高度
        updateHeight(node);
//        调整后继根节点高度
        updateHeight(right);

        return right;
    }

    /**
     * @param node
     * @return 左右旋 LR
     * 左边高L，左边右子树高R
     */
    private AVLNode leftRightRotate(AVLNode node) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    /**
     * @param node
     * @return 右左旋 RL
     * 右边高R，右边左子树高L
     */
    private AVLNode rightLeftRotate(AVLNode node) {
        node.right = rightRotate(node.right);
        return rightRotate(node);
    }

    /**
     * @param node
     * @return 平衡
     */
    private AVLNode balance(AVLNode node) {
        if (node == null) {
            return null;
        }
        int bf = bf(node);
        //LL
        if (bf > 1 && bf(node.left) >= 0) {
            return rightRotate(node);
            //LR
        } else if (bf > 1 && bf(node.left) < 0) {
            return leftRightRotate(node);
            //RL
        } else if (bf < -1 && bf(node.right) > 0) {
            return rightLeftRotate(node);
            //RR
        } else if (bf < -1 && bf(node.right) <= 0) {
            return leftRotate(node);
        }
        return node;
    }

    /**
     * @param key
     * @param value 添加数据
     */
    public void put(int key, Object value) {
        root = doPut(root, key, value);
    }

    private AVLNode doPut(AVLNode root, int key, Object value) {
        if (root == null) {
            return new AVLNode(key, value);
        }
        if (root.key == key) {
            return root;
        }
        if (root.key > key) {
            root.left = doPut(root.left, key, value);
        } else {
            root.right = doPut(root.right, key, value);
        }
        updateHeight(root);
        return balance(root);
    }

    private void tree(AVLNode root, List<Object> list) {
        if (root == null) {
            return;
        }
        tree(root.left, list);
        list.add(root.value);
        tree(root.right, list);
    }

    /**
     * @return list
     * 获取树上每个节点值
     */
    public List<Object> getTree() {
        List<Object> list = new ArrayList<>();
        tree(root, list);
        return list;
    }

    /**
     * @param key
     * @return 删除
     */
    public Object remove(int key) {
        AVLNode value = deRemove(root, key);
        root = value;
        return value.value;
    }

    private AVLNode deRemove(AVLNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.key > key) {
            root.left = deRemove(root.left, key);
        } else if (root.key < key) {
            root.right = deRemove(root.right, key);
        } else {
//            四种情况
            if (root.right == null) {
                root = root.left;
            } else if (root.left == null) {
                root = root.right;
            } else {
                AVLNode node = root.right;
                while (node.left != null) {
                    node = node.left;
                }
                node.right = deRemove(node.right, node.key);
                node.left = root.left;
                root = node;
            }
        }
        if (root == null) {
            return null;
        }
        updateHeight(root);
        return balance(root);
    }

    /**
     * @param key
     * @return object
     * <p>根据key获取值</p>
     */
    public Object Get(int key) {
        if (String.valueOf(key) == null) {
            return null;
        }
        AVLNode bstNode = root;
        while (bstNode != null) {
            if (bstNode.key > key) {
                bstNode = bstNode.left;
            } else if (bstNode.key < key) {
                bstNode = bstNode.right;
            } else {
                return bstNode.value;
            }
        }
        return null;
    }

    /**
     * @return V
     * 获取二叉树最大值
     * Gets the maximum value of the binary tree
     */
    public Object MaxValue() {
        return MaxValue(this.root);
    }

    private Object MaxValue(AVLNode root) {
        if (root == null) {
            return null;
        }
        AVLNode avlNode = root;
        while (avlNode.right != null) {
            avlNode = avlNode.right;
        }
        return avlNode.value;
    }

    /**
     * @return V
     * 获取二叉树最小值
     * Gets the minimum value of the binary tree
     */
    public Object MinValue() {
        return MinValue(this.root);
    }

    private Object MinValue(AVLNode root) {
        if (root == null) {
            return null;
        }
        AVLNode avlNode = root;
        while (avlNode.left != null) {
            avlNode = avlNode.left;
        }
        return avlNode.value;
    }

}
